import java.util.*;


class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String ,Integer> map=new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            if(!map.containsKey(words[i])){
                map.put(words[i],1);
            }else{
                int val=map.get(words[i]);
                map.put(words[i],val+1);
            }
        }
        PriorityQueue<Map.Entry<String,Integer>> priorityQueue=new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue())==0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getKey().compareTo(o2.getKey());
            }
        });
        for (Map.Entry<String,Integer> entry: map.entrySet()) {
            if(priorityQueue.size()<k){
                priorityQueue.offer(entry);
            }else{
                if(priorityQueue.peek().getValue().compareTo(entry.getValue())<0){
                    priorityQueue.poll();
                    priorityQueue.offer(entry);
                }else {
                    if(priorityQueue.poll().getValue().compareTo(entry.getValue())==0){
                        if(priorityQueue.peek().getKey().compareTo(entry.getKey())>0){
                            priorityQueue.poll();
                            priorityQueue.offer(entry);
                        }
                    }
                }
            }
        }
        List<String> list=new ArrayList<>();
        for (int i = 0; i < k; i++) {
            list.add(priorityQueue.poll().getKey());

        }
        Collections.reverse(list);
        return list;

    }
}